package 堆;

import com.sun.xml.internal.bind.v2.util.CollisionCheckStack;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author shy_black
 * @date 2019/4/25 15:24
 * @Description:
 */
public class MinHeap<E extends Comparable<E>> {
    private ArrayList<E> data;
    public MinHeap() {
        data = new ArrayList<>();
    }
    public MinHeap(int capacity) {
        data = new ArrayList<>(capacity);
    }
    //求父节点，左右子树节点
    public int parent(int index) {
        if(index < 0 || index >data.size())
            throw new IllegalArgumentException("非法index");
        return (index-1)/2;
    }
    public int leftChild(int index) {
        return index*2 + 1;
    }
    public int rightChile(int index) {
        return index*2 + 2;
    }
    public boolean isEmpty() {
        return data.isEmpty();
    }
    public int size() {
        return data.size();
    }
    //向堆中添加元素
    public void add(E e) {
        data.add(e);
        siftUp(data.size()-1);
    }
    public void siftUp(int index) {
        while(index > 0 &&
                data.get(index).compareTo(data.get(parent(index))) < 0) {
            swap(index,parent(index));
        }
    }
    public void swap(int i,int j) {
        Collections.swap(data,i,j);
    }
    //查看堆顶元素
    public E peek() {
        return data.get(0);
    }
    //删除堆顶元素
    public void extractMin() {
        data.set(0,data.get(size()-1));
        data.remove(size()-1);
        siftDown(0);

    }
    private void siftDown(int index) {
        while(leftChild(index)  < data.size()) {
            int j = leftChild(index);
            if(data.get(leftChild(index)).compareTo(data.get(rightChile(index))) > 0) {
                //找左右节点中相对较小的
                j = rightChile(index);
            }
            //如果较小的小于index，交换
            //index = j 进行下一轮循环
            if(data.get(index).compareTo(data.get(j)) > 0) {
                swap(index, j);
                index = j;
            }
            else
                break;

        }
    }
    public void replace(E e) {
        data.set(0,e);
        siftDown(0);
    }
    // 找最后一个叶子节点的父节点开始向上遍历，siftUp
    public void heapify() {
        for(int i = parent(size()-1);i >= 0 ;i--) {
            siftDown(i);
        }
    }
}
